# LeetCode 860、柠檬水找零
# 一、题目描述
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。
你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 柠檬水找零（ LeetCode 860 ）:https://leetcode-cn.com/problems/lemonade-change/
class Solution {
public boolean lemonadeChange(int[] bills) {
// 用来记录 5 元钞票的数量
int five = 0;
// 用来记录 10 元钞票的数量
int ten = 0;
// 顾客开始按顺序购买，并找零
for(int i = 0 ; i < bills.length ; i++){
// 1、如果发现是 5 元面额
if(bills[i] == 5){
// 那么可以直接收钱，不需要找零
// 并且 5 元钞票的数量加 1
five++;
// 2、如果发现是 10 元面额
}else if(bills[i] == 10){
// 如果手中有 5 元钞票，则找零 5 元
if(five > 0){
// 5 元钞票的数量减 1
five--;
// 10 元钞票的数量加 1
ten++;
}else{
// 如果手中没有 5 元钞票，说明找零失败
return false;
}
// 3、如果发现是 20 元面额
}else{
// 如果手中有 10 元 和 5 元钞票，则找零 1 张 10 元和 1 张 5 元的钞票
if(ten > 0 && five > 0){
// 5 元钞票的数量减 1
five--;
// 10 元钞票的数量减 1
ten--;
}else{
// 如果手中只有 5 元的，并且数量超过或者等于 3 张
// 那么找零 3 张 5 元的钞票
if(five >= 3){
// 5 元钞票的数量减 3
five -= 3;
}else{
// 说明这个时候顾客付 20 元的时候
// 1、手中没有 1 张 10 元的和 1 张 5 元的
// 2、手中没有 3 张 5 元的
// 说明找零失败
return false;
}
}
}
}
// 所有顾客都找零了，成功
return true;
}
}
# **2、**C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 柠檬水找零（ LeetCode 860 ）:https://leetcode-cn.com/problems/lemonade-change/
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
// 用来记录 5 元钞票的数量
int five = 0;
// 用来记录 10 元钞票的数量
int ten = 0;
// 顾客开始按顺序购买，并找零
for(int i = 0 ; i < bills.size() ; i++){
// 1、如果发现是 5 元面额
if(bills[i] == 5){
// 那么可以直接收钱，不需要找零
// 并且 5 元钞票的数量加 1
five++;
// 2、如果发现是 10 元面额
}else if(bills[i] == 10){
// 如果手中有 5 元钞票，则找零 5 元
if(five > 0){
// 5 元钞票的数量减 1
five--;
// 10 元钞票的数量加 1
ten++;
}else{
// 如果手中没有 5 元钞票，说明找零失败
return false;
}
// 3、如果发现是 20 元面额
}else{
// 如果手中有 10 元 和 5 元钞票，则找零 1 张 10 元和 1 张 5 元的钞票
if(ten > 0 && five > 0){
// 5 元钞票的数量减 1
five--;
// 10 元钞票的数量减 1
ten--;
}else{
// 如果手中只有 5 元的，并且数量超过或者等于 3 张
// 那么找零 3 张 5 元的钞票
if(five >= 3){
// 5 元钞票的数量减 3
five -= 3;
}else{
// 说明这个时候顾客付 20 元的时候
// 1、手中没有 1 张 10 元的和 1 张 5 元的
// 2、手中没有 3 张 5 元的
// 说明找零失败
return false;
}
}
}
}
// 所有顾客都找零了，成功
return true;
}
};
# 3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https:#www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 柠檬水找零（ LeetCode 860 ）:https:#leetcode-cn.com/problems/lemonade-change/
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
# 用来记录 5 元钞票的数量
five = 0
# 用来记录 10 元钞票的数量
ten = 0
# 顾客开始按顺序购买，并找零
for i in range(len(bills)) :
# 1、如果发现是 5 元面额
if bills[i] == 5 :
# 那么可以直接收钱，不需要找零
# 并且 5 元钞票的数量加 1
five += 1
# 2、如果发现是 10 元面额
elif bills[i] == 10 :
# 如果手中有 5 元钞票，则找零 5 元
if five > 0 :
# 5 元钞票的数量减 1
five -= 1
# 10 元钞票的数量加 1
ten += 1
else :
# 如果手中没有 5 元钞票，说明找零失败
return False
# 3、如果发现是 20 元面额
else :
# 如果手中有 10 元 和 5 元钞票，则找零 1 张 10 元和 1 张 5 元的钞票
if ten > 0 and five > 0 :
# 5 元钞票的数量减 1
five -= 1
# 10 元钞票的数量减 1
ten -= 1
else:
# 如果手中只有 5 元的，并且数量超过或者等于 3 张
# 那么找零 3 张 5 元的钞票
if five >= 3 :
# 5 元钞票的数量减 3
five -= 3
else :
# 说明这个时候顾客付 20 元的时候
# 1、手中没有 1 张 10 元的和 1 张 5 元的
# 2、手中没有 3 张 5 元的
# 说明找零失败
return False
# 所有顾客都找零了，成功
return True
# 四、复杂度分析
时间复杂度：O(N)，其中 N 是 bills 的长度。
空间复杂度：O(1)。